package a07_二叉树;

/**
 * <p>
 * a30_删除二叉搜索树中的节点
 * </p>
 *
 * @author flyduck
 * @since 2024/12/25
 */
public class a30_删除二叉搜索树中的节点 {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(5,
                new TreeNode(3,
                        new TreeNode(2),
                        new TreeNode(4)),
                new TreeNode(6,
                        null,
                        new TreeNode(7))
        );
        TreeNode treeNode1 = deleteNode(treeNode, 5);

        System.out.println();

    }
    //1、没找到删除的节点
    //2、找到了删除的节点，叶子节点->左空右空
    //3、找到了删除的节点，非叶子节点
            //左不空右空：让父节点.left = node.left
            //左空右不空：让父节点.right = node.right
            //左不空右不空：
                //假设让右孩子继位
                //把左子树放在右子数最左侧的值的下面
    public static TreeNode deleteNode(TreeNode root, int key) {
        TreeNode node = findNode(root, key);
        if (node == null) {
            return root;//如果node不为null，直接返回
        }
        if (node.left == null && node.right == null) {
            if (parentNode == null) {
                return null;
            }else if (parentNode.left == node) {
                parentNode.left = null;
            }else {
                parentNode.right = null;
            }
        }else if(node.left != null && node.right == null){
            if (parentNode == null) {
                return node.left;
            }else if (parentNode.left == node) {
                parentNode.left = node.left;
            }else {
                parentNode.right = node.left;
            }
        }else if(node.left == null && node.right != null){
            if (parentNode == null) {
                return node.right;
            }else if (parentNode.left == node) {
                parentNode.left = node.right;
            }else {
                parentNode.right = node.right;
            }
        }else {
            TreeNode currentNode = node.right;
            while (currentNode.left != null){
                currentNode = currentNode.left;
            }

            currentNode.left = node.left;

            if (parentNode == null) {
                return node.right;
            }else if (parentNode.left == node) {
                parentNode.left = node.right;
            }else {
                parentNode.right = node.right;
            }
        }
        return root;
    }

    private static TreeNode parentNode;

    public static TreeNode findNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }

        if (key < root.val) {
            parentNode = root;
            return findNode(root.left,key);
        }else if(key > root.val){
            parentNode = root;
            return findNode(root.right,key);
        }else {
            return root;
        }
    }
}
